#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;
/*
 *输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。



参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3
示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true
 * */

// 例子[1 3 2 左边][6右边][5根节点] --下面不用看了 是根据这个来的
// 后序遍历 左边 右边 跟节点 倒序为跟 右边 左边
// 先序 倒过来 跟右左 5 6 2 3 1

bool recur(vector<int> &postorder) {
    //获取根节点
    if (postorder.size() <= 1)
        return true;

    int root = postorder.back();//获取跟节点
    postorder.pop_back();
    //开始check
    // 说明了存在右边子树 就开始寻找中间那个跟
    vector<int> left;
    vector<int> right;
    if (root < postorder.back()) {
        //记录 index
        int leftIndex = 0;
        for (int i = 0; i < postorder.size(); ++i) {
            if (postorder[i] > root) {
                leftIndex = i;
                break;
            }
            if (postorder[i] == root)
                return false;
        }

        // 开始寻找右边子树
        for (int i = leftIndex; i < postorder.size(); ++i) {
            if (postorder[i] <= root)
                return false;
        }

        //构造左边右边子树进行递归check
        left.assign(postorder.begin(), postorder.begin() + leftIndex);
        right.assign(postorder.begin() + leftIndex, postorder.end());
    } else {
        if (root == postorder.back())
            return false;

        //否则都是左边子树

        for (int i = 0; i < postorder.size(); ++i) {
            if (postorder[i] >= root)
                return false;

        }
        left.assign(postorder.begin(), postorder.end());

    }

    return recur(left) && recur(right);

}

bool verifyPostorder(vector<int> &postorder) {

    return recur(postorder);
}